1. Field of Invention
The present invention relates to a signal encoding method, a signal decoding method, a signal encoding apparatus, a signal decoding apparatus, a signal encoding program, and a signal decoding program suitably applicable to image transmission systems such as mobile video transmission systems.
2. Related Background of the Invention
The conventionally known methods of encoding moving pictures include International Standards of video coding such as the ITU-T H.26x series, the ISO/IEC MPEG series, and so on. These video coding methods are configured to process each of images of macroblocks obtained by dividing a frame image, by predetermined data transformation operations including Motion Compensation (MC) and Discrete Cosine Transform (DCT), so as to create image data as an object of coding.
The image data created by the data transformation operations is further subjected to entropy coding to obtain encoded data which is compressed data used in picture transmission. Arithmetic Coding (AC) is used as one of such entropy coding methods. The arithmetic coding will be outlined below, but reference should be made as to the details of the arithmetic coding to “The Data Compression Book” authored by M. Nelson and J.-L. Gailley and translated by Takeshi Ogiwara and Suguru Yamaguchi, and others.
In general, where the arithmetic coding is effected on an information source sequence (symbol sequence) as a combination of plural types of symbols, the symbols are first assigned respective fixed intervals according to probabilities of occurrence of the symbols, on a number line (probability number line) of [0.0, 1.0). At this time, a table indicating the correspondence between the symbols and the intervals on the number line is called a probability table. The information source sequence is entropy coded by the arithmetic coding with reference to this probability table, so as to create a code word as an expression of the information source sequence on the number line.
Let us explain the arithmetic coding herein with reference to FIGS. 14-16. Specifically, the arithmetic coding will be explained with an example in which a character string “ARITHMETIC” is an information source sequence as an object of coding and is encoded by the arithmetic coding.
There appear eight types of characters (symbols) of A, C, E, H, I, M, R, and T in the above information source sequence. These letters are assigned respective intervals on the number line (probability number line) of [0.0, 1.0), as shown in the table of FIG. 14, so that the intervals have respective lengths proportional to probabilities of occurrence of the respective letters in the letter string. The table shown in FIG. 14 to illustrate the correspondence between the letters and the intervals on the number line is the probability table used in the arithmetic coding.
FIG. 15 is a diagram showing the coding of the letter string “ARITHMETIC” through the use of the probability table shown in FIG. 14. In the arithmetic coding, interval reduction operations based on the probability table are successively carried out for the respective symbols in the information source sequence, so as to generate a code word as encoded data of the information source sequence.
In the example shown in FIG. 15, for the first letter “A” in the character string “ARITHMETIC” as an object of coding, the interval [0, 1) on the number line is first divided into eight intervals corresponding to the respective letters with reference to the probability table shown in FIG. 14. Then the interval is reduced to the interval [0.0, 0.1) corresponding to the letter “A” among those intervals. Next, for the second letter “R,” the interval [0.0, 0.1) is divided into eight intervals. Then the interval is reduced to the interval [0.07, 0.08) corresponding to the letter “R” among those intervals.
Thereafter, coding operations by this interval reduction are successively carried out for the respective letters. Then we finally obtain the interval [0.0757451536, 0.0757451552) on the number line and the number “0.0757451536” in the interval is generated as a code word as a result of the arithmetic coding of the letter string “ARITHMETIC.”
FIG. 16 is a diagram showing the decoding of the code word “0.0757451536” into the letter string “ARITHMETIC” with the probability table shown in FIG. 14.
In the example shown in FIG. 16, the interval [0.0, 0.1) of the interval length 0.1 including the code word is first identified from the code word “0.0757451536” as an object of decoding, with reference to the probability table shown in FIG. 14. Then the letter “A” corresponding to the identified interval is outputted as the first letter and a new code word “0.757451536” is generated according to (code word-lower limit)/(interval length). Then, from the code word “0.757451536,” the interval [0.7, 0.8) of the interval length 0.1 including the code word is identified with reference to the probability table. The letter “R” corresponding to the identified interval is outputted as the second letter and a new code word “0.57451536” is generated.
Thereafter, such decoding operations are successively carried out for the code word. It results in restoring the letter string “ARITHMETIC” from the arithmetic coded data of the code word “0.0757451536.”
As described above, the entropy coding of the information source sequence by the arithmetic coding involves making the correspondence between symbols in the information source sequence and intervals on the number line, whereby it can express any information source sequence by a code word on the number line of [0.0, 1.0]. By setting the probability table providing the correspondence between symbols and intervals according to probabilities of occurrence of respective symbols, it is feasible to efficiently carry out the entropy coding of the information source sequence and thereby increase the efficiency of data compression by coding.